#include <stdio.h>
#include <malloc.h>

typedef struct P
{
    float coef;//系数
    int expn;  //指数
    struct P *next;//指针域
}Algebraic_node;//代数式

typedef struct
{
    Algebraic_node *head;/*头指针*/
    size_t length;/*当前长度*/
}Polynomial_list;


/*创建节点*/
Algebraic_node* CreateNode(float coef,int expn)
{
    Algebraic_node *new_node = (Algebraic_node *)malloc(sizeof(Algebraic_node));
    if (new_node == NULL)
    {
        perror("new_node == NULL");
        return NULL;
    }
    
    new_node->coef = coef;
    new_node->expn = expn;
    new_node->next = NULL;

    return new_node;
}


/*销毁节点*/
void DestroyNode(Algebraic_node *node)
{
    free(node);
}

/*初始化链表*/
void InitList(Polynomial_list **list)
{
    *list  = (Polynomial_list *)malloc(sizeof(Polynomial_list));
    (*list)->head = NULL;
    (*list)->length = 0;
}

/*销毁链表*/
void DestroyList(Polynomial_list **list)
{
    while ((*list)->head)
    {
        Algebraic_node *temp_node = (*list)->head;
        DestroyNode(temp_node);
        (*list)->head = (*list)->head->next;
    }
    
    free(*list);
    *list = NULL;
}

/*尾部插入*/
Polynomial_list* PushBackNode(Polynomial_list *list,float coef,int expn)
{
    Algebraic_node *node = CreateNode(coef,expn);

    if (node == NULL)
    {
        perror("fail");
    }

    Algebraic_node *current_node = list->head;

    if (current_node == NULL)
    {
        list->head = node;
    }
    else
    {
        while (current_node->next)//当前下一个不为空，跳出时为最后一个节点
        {
            current_node = current_node->next;
        }

        current_node->next = node;//尾插
        
    }
    list->length ++;
    
    return list;
}

/*获取链表长度*/
size_t getListLength(Polynomial_list *list)
{
    if (!list)
    {
        perror("fail");
    }
    
    Algebraic_node *temp = list->head;
    size_t length = 0;
    while (temp)
    {
        length ++;
        temp = temp->next;
    }
    
    return length;
}

/*打印链表数据*/
void PrintListData(Polynomial_list *list)
{
    if (!list)
    {
        perror("fail");
    }
    Algebraic_node *temp_node = list->head;
    printf("\nPrint Polynomial:\n");
    while (temp_node)
    {
        printf("(%0.1f,%d)   ",temp_node->coef,temp_node->expn);
        temp_node = temp_node->next;
    }
    printf("\n");
}


/*创建多项式*/
void CreateListData(Polynomial_list *list,int n)
{
    if (!list || (n < 1))
    {
        /* code */
    }
    
    int count = 0;
    printf("Input data for polynomial list\n");
    while (count < n)
    {
        count ++;
        float coef = 0.0;
        int expn = 0;
        printf("Input data for polynomial list count %d\n",count);
        scanf("%f,%d",&coef,&expn);
        PushBackNode(list,coef,expn);
    }
    
}

/*多项式相加之前需要先排序：按照指数依次升序*/
/*快慢指针找中点*/
Algebraic_node *FindMiddle(Algebraic_node *head)
{
    if (!head)
    {
        return head;
    }
    
    Algebraic_node *slow = head;
    Algebraic_node *fast = head->next;

    if (!fast)
    {   
        return head;  
    } 

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

/*合并两个有序链表*/
Algebraic_node* MergeList(Algebraic_node *left, Algebraic_node *right)
{  
    if (left == NULL) return right;  
    if (right == NULL) return left;  
  
    Algebraic_node *result = NULL;  
  
    if (left->expn <= right->expn) {  
        result = left;  
        result->next = MergeList(left->next, right);  
    } else {  
        result = right;  
        result->next = MergeList(left, right->next);  
    }  
    return result;  
}  

/*归并排序*/
Algebraic_node* MergeSortList(Algebraic_node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    /*快慢指针找中点*/
    Algebraic_node *middle = FindMiddle(head);

    Algebraic_node *right = middle->next;/*右边*/
    middle->next = NULL;/*中间开始断开链表*/

    Algebraic_node *Left = MergeSortList(head);
    Algebraic_node *Right =  MergeSortList(right);
    
    return MergeList(Left,Right);
}

/*多项式相加*/
Polynomial_list* Polynomial_add(Polynomial_list *list1,Polynomial_list *list2)
{
    /*初始条件*/
    if (!list1 || !list2 || !list1->head || !list2->head)
    {
        return list1;
    }
    
    /*构造一条链表作为作为返回表*/
    Polynomial_list *list = NULL;
    InitList(&list);
    Algebraic_node *node1 = list1->head;
    Algebraic_node *node2 = list2->head;

    while (node1 && node2)
    {
        if(node1->expn == node2->expn)/*指数相等*/
        {
            PushBackNode(list,(node1->coef + node2->coef),node1->expn);/*系数相加*/
            node1 = node1->next;
            node2 = node2->next;
        }
        else if(node1->expn < node2->expn)/*指数小于*/
        {
            PushBackNode(list,node1->coef,node1->expn);
            node1 = node1->next;

        }
        else/*指数大于*/
        {
            PushBackNode(list,node2->coef,node2->expn);
            node2 = node2->next;
        }
    }

    Algebraic_node *end = list->head;
    while (end->next)/*最后一个节点*/
    {
        end = end->next;
    }
    
    end->next = node1 ? node1 : node2;/*剩余的节点*/
    
    return list;
}


int main(int argc, char const *argv[])
{
    Polynomial_list *list1;
    Polynomial_list *list2;
    InitList(&list1);
    InitList(&list2);

    //CreateListData(list,5);
    PushBackNode(list1,1,0);
    PushBackNode(list1,1,4);
    PushBackNode(list1,1,3);
    PushBackNode(list1,1,1);
    PushBackNode(list1,1,5);
    PushBackNode(list1,1,2);
    
    PushBackNode(list2,1,0);
    PushBackNode(list2,1,4);
    PushBackNode(list2,1,3);
    PushBackNode(list2,1,1);
    PushBackNode(list2,1,5);
    PushBackNode(list2,1,2);
    PushBackNode(list2,1,6);
    PushBackNode(list2,1,8);

    PrintListData(list1);
    PrintListData(list2);

    list1->head = MergeSortList(list1->head);
    list2->head = MergeSortList(list2->head);

    PrintListData(list1);
    PrintListData(list2);

    Polynomial_list *list = Polynomial_add(list1,list2);
    PrintListData(list);
    return 0;
}



